/**
 * 选择排序算法
 * 时间复杂度: O(n²)
 * 空间复杂度: O(1)
 * @param {Array} arr - 需要排序的数组
 * @returns {Array} - 排序后的数组
 */
function selectionSort(arr) {
    // 创建数组副本，避免修改原数组
    const array = [...arr];
    const length = array.length;
    
    // 外层循环，每次找到最小元素放到已排序部分的末尾
    for (let i = 0; i < length - 1; i++) {
        // 假设当前位置的元素是最小的
        let minIndex = i;
        
        // 内层循环，在未排序部分找到最小元素
        for (let j = i + 1; j < length; j++) {
            // 如果找到更小的元素，更新最小索引
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        
        // 如果最小元素不在当前位置，则交换
        if (minIndex !== i) {
            // 使用解构赋值进行交换
            [array[i], array[minIndex]] = [array[minIndex], array[i]];
        }
    }
    
    return array;
}

// 测试代码
function testSelectionSort() {
    console.log("=== 选择排序测试 ===");
    
    // 测试用例1：普通数组和负数
    const arr1 = [64, 34, 25, 12, 22, 11, 90, -5, 10, -3, 8, -1, 0, 4];
    console.log("原始数组:", arr1);
    console.log("排序后:", selectionSort(arr1));
    
    // 测试用例2：特殊情况数组（空数组、单元素数组、已排序数组）
    const arr2 = [];
    console.log("\n原始数组(空数组):", arr2);
    console.log("排序后:", selectionSort(arr2));
    console.log("\n原始数组(单元素):", [42]);
    
    console.log("排序后:", selectionSort([42]));
    console.log("\n原始数组(已排序):", [1, 2, 3, 4, 5]);
    console.log("排序后:", selectionSort([1, 2, 3, 4, 5]));
    
    // 测试用例3：包含重复元素的大数组
    const arr3 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, ...Array.from({length: 20}, () => Math.floor(Math.random() * 100))];
    console.log("\n原始数组:", arr3);
    console.log("排序后:", selectionSort(arr3));
}

// 运行测试
testSelectionSort();
// 插入排序算法
function insertionSort(array) {
    const length = array.length;
    
    // 从第二个元素开始遍历
    for (let i = 1; i < length; i++) {
        // 保存当前要插入的元素
        const current = array[i];
        let j = i - 1;
        
        // 将比当前元素大的元素都向后移动一位
        while (j >= 0 && array[j] > current) {
            array[j + 1] = array[j];
            j--;
        }
        
        // 在正确的位置插入当前元素
        array[j + 1] = current;
    }
    
    return array;
}

// 测试插入排序
function testInsertionSort() {
    console.log("\n=== 插入排序测试 ===");
    
    // 测试用例1：普通数组
    const arr1 = [64, 34, 25, 12, 22, 11, 90];
    console.log("原始数组:", arr1);
    console.log("排序后:", insertionSort(arr1));
    
    // 测试用例2：已排序数组
    const arr2 = [1, 2, 3, 4, 5];
    console.log("\n原始数组:", arr2);
    console.log("排序后:", insertionSort(arr2));
    
    // 测试用例3：逆序数组
    const arr3 = [5, 4, 3, 2, 1];
    console.log("\n原始数组:", arr3);
    console.log("排序后:", insertionSort(arr3));
    
    // 测试用例4：包含重复元素的数组
    const arr4 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
    console.log("\n原始数组:", arr4);
    console.log("排序后:", insertionSort(arr4));
    
    // 测试用例5：空数组
    const arr5 = [];
    console.log("\n原始数组:", arr5);
    console.log("排序后:", insertionSort(arr5));
}

// 运行测试
testInsertionSort();
